package 单调栈;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

//84 柱状图中最大矩形
public class Solution5 {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        int[] rights = new int[n];
        Arrays.fill(rights, n);
        Deque<Integer> stack = new LinkedList();
        for (int i = 0 ; i < n ; i++){
            while (!stack.isEmpty() && heights[stack.getLast()] > heights[i]) {
                int top = stack.pollLast();
                rights[top] = i;
            }
            stack.addLast(i);
        }
        int[] left = new int[n];
        Arrays.fill(left, -1);
        stack.clear();
        for (int i = n - 1 ; i >= 0 ; i--) {
            while (!stack.isEmpty() && heights[stack.getLast()] > heights[i]) {
                int top = stack.pollLast();
                left[top] = i;
            }
            stack.addLast(i);
        }
        int res = 0;
        for (int i = 0 ; i < n ; i++) {
            res = Math.max(res,  (rights[i] - left[i] - 1) * heights[i]);
        }
        return res;
    }
}
